---
title: 字符串匹配
---


字符串匹配算法有很多，比较简单的有两种 BF 算法和 RK 算法。比较难理解，但是更加高效的也有两种，分别是 BM 算法和 KMP 算法。

## BF 算法
BF 算法中的 BF 是 Brute Force 的缩写，中文叫做暴力匹配算法，也叫朴素匹配算法。这种算法的字符串匹配方式很暴力，简单、好懂，但相应的性能也不高。

:::tip 主串和模式串
比方说，我们在字符串 A 中查询字符串 B，那么字符串 A 就是主串，字符串 B 就是模式串。把主串的长度记为  n，模式串的长度记为 m。因为是从主串中找模式串，所以 m>n。
:::

**BF 算法的思想可以用一句话概况：在主串中，检查起始位置分别是 0、1、2...n-m 且长度为 m 的 n-m+1 个子串，看有没有模式匹配的。**

<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/img/202410081811642.png"/>

从上面的算法思想例子，可以看出，比如主串是 ”aaaaa...aaaaaa“,，模式串是 ”aaaaab“。每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏时间复杂度是 O(m*n)。

尽管在理论上，BF 算法的时间复杂度很高，是 O（m*n）,但在实际的开发中，它却是一个比较常用的字符串匹配算法，原因有两点：
1. 在实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串和主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以停止了，不需要把 m 个字符都比较一下。所以，尽管理论上的最坏情况复杂度是 O(n*m),但是，统计意义上，大部分情况下，算法执行效率都会比这个高很多。
2. 朴素字符串匹配算法简单，代码实现也很简单。简单意味着不容易出错，如果有 bug 也很容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。这也就是 KISS 设计原则。



```java title='朴素模式匹配算法'
/**
 * 朴素的模式匹配算法
 * @param text
 * @param pattern
 */
public static void naivePatternMatching(String text, String pattern) {
   // 维护一个主串的检查点，从 0 开始
    int i = 0;
    while (i <= text.length() - pattern.length()) {
        boolean found =  true;
        // 从 i 开始，逐个字符判断是否匹配
        for (int j = 0; j < pattern.length(); j++) {
             if (text.charAt(i + j) != pattern.charAt(j)) {
                 found = false;
                 break;
             }
        }
        if (found) {
            System.out.println("匹配成功，起始位置为：" + i);
        }
        i++;
    }
}
```
## BM 算法
### BM 算法的核心思想
我们把模式串和主串的匹配过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。如下图：


<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/4316dd98eac500a01a0fd632bb5e77f9.jpg"/>

在这个例子中，主串中的 c，在模式串中是不存在的，所以，模式串往后滑动的时候，只要 c 与模式串没有重合，肯定无法匹配。所以，我们可以一次性把模式串往后多滑动几位，把模式串移动到 c 的后面。

<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/cf362f9e59c01aaf40a34d2f10e1ef15.jpg"/>

当遇到不匹配的字符时，可以将模式串往后多滑动几位，匹配的效率就提高了。

### BM 算法原理解析
BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。
#### 1. 坏字符规则
在匹配的时候，我们都是按模式串的下标从小到大的顺序，一次与主串中的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯，而 BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的。如下图：

<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/29521f541dd45e13162013b3364fece1.jpg"/>

<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/540809418354024206d9989cb6cdd89e.jpg"/>

从模式串的末尾往前倒着匹配，当发现某个字符没法匹配的时候，我们把这个没有匹配的字符叫做坏字符（主串中的字符）。

<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/220daef736418df84367215647bca5da.jpg"/>

我们拿坏字符 c 在模式串中查找，发现模式串中并不存在这个字符，也就是说，字符 c 与模式串中的任何字符都不可能匹配。这个时候，我们可以将模式串直接往后滑动三位，将模式串滑动到 c 后面的位置，再从模式串的末尾字符开始比较。

<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/4e36c4d48d1b6c3b499fb021f03c7f64.jpg"/>

这个时候，我们发现，模式串中的最后一个字符 d ， 还是无法跟主串中的 a 匹配，这个时候，因为坏字符 a 在模式串中是存在的，模式串中
## KMP 算法
